package com.czk.tree.huffmantree.practice.tree;

import lombok.Data;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @Author:ChenZhangKun
 * @Date: 2021/6/27 23:28
 */
public class HuffManTree {
    public static void main(String[] args) {
        int[] array={13,7,8,3,29,6,1};
        Node huffManTree = createHuffManTree(array);
        huffManTree.preTraverse();
    }
    public static Node createHuffManTree(int[] array){
        // 创建集合
        List<Node> list=new ArrayList<>(10);
        for (int i : array) {
            Node node=new Node(i);
            list.add(node);
        }
        // 遍历
        while (list.size()>1){
            // 排序
            Collections.sort(list);
            // 拿到第一个
            Node left=list.get(0);
            Node right=list.get(1);
            // 构建新node
            Node newNode=new Node(left.value+right.value);
            newNode.left=left;
            newNode.right=right;
            list.remove(left);
            list.remove(right);
            list.add(newNode);
        }
        return list.get(0);
    }
}
@Data
class Node implements Comparable<Node>{
    // 节点权值
    int value;
    // 左子节点
    Node left;
    // 指向右子节点
    Node right;

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    @Override
    public int compareTo(Node o) {
        // 从小到大排序
        return this.value-o.value;
    }
    // 前序遍历
    public void preTraverse(){
        System.out.print(this.value+" ");
        if (this.left!=null){
            this.left.preTraverse();
        }
        if (this.right!=null){
            this.right.preTraverse();
        }
    }
}
